package com.cat.greedyAlgorithm;

import java.util.HashMap;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/distant-barcodes/description/
 * @create 2025/10/12 15:02
 * @since JDK17
 */

public class Solution84 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 0, cnt = 0, n = barcodes.length;
        for (int num : barcodes) {
            map.merge(num, 1, Integer::sum);
            int x = map.get(num);
            if (x > cnt) {
                cnt = x;
                max = num;
            }
        }
        int i = 0;
        while (cnt-- > 0) {
            barcodes[i] = max;
            i += 2;
        }
        for (var e : map.entrySet()) {
            int x = e.getKey(), y = e.getValue();
            if (x == max) {
                continue;
            }
            while (y-- > 0) {   // 一个一个分配
                if (i >= n) {
                    i = 1;
                }
                barcodes[i] = x;
                i += 2;
            }
        }

        return barcodes;
    }
}
